#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time     : 2021-01-03 14:37
# @Author   : link-yang
# @File     : 2020-01-03.86. 分隔链表
# @Software : PyCharmCE
from tools.my_methods import *


# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        h1, t1, h2, t2 = None, None, None, None
        p, q = None, head
        while q:
            p, q = q, q.next
            if p.val < x:
                if h1:
                    t1.next = p
                    p.next = None
                    t1 = p
                else:
                    h1 = p
                    t1 = p
                    p.next = None
            else:
                if h2:
                    t2.next = p
                    p.next = None
                    t2 = p
                else:
                    h2 = p
                    t2 = p
                    p.next = None
        if h1:
            t1.next = h2
        else:
            h1 = h2
        return h1
